package Niuke;

public class Trie{

    class TrieNode{
        int path;
        int end;
        TrieNode[] nexts;

        public TrieNode(){
            path=0;
            end=0;
            nexts=new TrieNode[26];
        }
    }
    TrieNode root;
    public Trie() {
        root=new TrieNode();
    }

    public void insert(String word) {
        TrieNode p=root;
        for (int i=0;i<word.length();i++){
            char tmp=word.charAt(i);
            if (p.nexts[tmp-'0']==null)
                p.nexts[tmp-'0']=new TrieNode();
            p.nexts[tmp-'0'].path++;
            p=p.nexts[tmp-'0'];
        }
        p.end++;
    }

    public boolean search(String word) {
        TrieNode p=root;
        for (int i=0;i<word.length();i++){
            int tmp=word.charAt(i)-'0';
            if (p.nexts[tmp]==null)
                return false;
            p=p.nexts[tmp];
        }
        return p.end>0?true:false;
    }

    public boolean startsWith(String prefix) {
        TrieNode p=root;
        for (int i=0;i<prefix.length();i++){
            int tmp=prefix.charAt(i)-'0';
            if (p.nexts[tmp]==null)
                return false;
            p=p.nexts[tmp];
        }
        return true;
    }

}
